package com.duing.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 3, 2, 5, 7, 6, 8, 9};
        TreeNode node1 = MergeTree.createByArray(arr, 0);
        List<List<Integer>> result = levelOrder(node1);
        System.out.println(result.toString());
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        // 遍历使用的队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        // 一次性处理完一层节点
        while (queue.size() > 0) {
            // 根据队列中的元素个数  获取在二叉树当前层级上的节点个数
            int n = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}
